home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The X-Philes (2nd Revision)
/
The X-Philes Number 1 (1995).iso
/
xphiles
/
hp48hor1
/
prime2.doc
< prev
next >
Wrap
Text File
|
1995-03-31
|
3KB
|
77 lines
(Comp.sys.handhelds)
Item: 1375 by kskalb at faui1f.informatik.uni-erlangen.de
Author: [Klaus Kalb]
Subj: HP48: primality testing
Date: Fri Dec 07 1990 07:56
This program for the HP48 tests numbers for being prime.
It is written as a user defined function, so you can include
it into algebraics.
Start it with a number (binary or real) in level 1 and it will answer:
0 if the number is composite
1 if the number is prime
2 if it can't do the job
The last case occurs only if the number is greater than 25*10^9.
Even if this occurs, you can be quite sure that the given number
is a prime, since the numbers that give a 2 on this test and are
composite are very rare --- but they do exist.
(they are indeed so rare that I don't know an example ;-)
This test is fast --- testing a prime near 10^9 will take about 7000 ticks.
This is less then one second --- not so bad for a small machine.
Of course this is accomplished using mcode. You need ASC\-> to get it
into your machine. [already ASC'd; you don't need to. -jkh-]
------------------------------------------------------------------------------
MORE ABOUT THE IMPLEMENTATION:
This program implements the test proposed by Pomerance, Selfridge and
Wagstaff in _The_Pseudoprimes_to_25*10^9_ in math.comp.35 (1980)
Some special effort is made to recognize small primes and numbers with
small factors on an early stage.
It will recognize all primes below 25*10^9.
It runs the strong pseudoprime test with the bases 2,3,5,7, so that
a number passing this test with result 2 is at least a strong pseudoprime
to these bases.
There are two subroutines written in mcode:
BGCD calculates the greatest common divisor of two binary integers.
It uses the binary algorithm that can be found in Knuth's
_The_Art_of_Computer_Programming.
MILRAB performs a strong pseudoprime test on the number N in level 2
to the base B in level 1. It will accept any combination of
binary integers and reals. The output is 1 if N is a
strong base-B pseudoprime and 0 if not.
Both routines perform argument checking and give decent error messages.
[The primality testing function itself is called 'PRIME?'. -jkh-]
------------------------------------------------------------------------------
DISCLAIMER: (that's one I've found on the net ;-)
This program makes use of undocumented low-level features of
the HP48SX calculator, and may or may not cause loss of data,
excessive battery drainage, and/or damage to the calculator
hardware. The Author takes no responsibility whatsoever for
any damage caused by the use of this program.
This software is provided "as is" and WITHOUT ANY EXPRESS OR
IMPLIED WARRANTIES, including, but not limited to, THE IMPLIED
WARRANTIES OF MERCHANTABILITY and FITNESS FOR A PARTICULAR PURPOSE.
------------------------------------------------------------------------------
Klaus Kalb | mail : IMMD1 / Martenstr. 3 / W-8520 Erlangen / Germany
| email: kskalb@immd1.informatik.uni-erlangen.de
------------------------------------------------------------------------------